package W328;

import java.util.*;

/**
 * @author zxc
 * @date 2023/01/15 11:57
 **/
public class CountGoodSorted {
    /**
     * 思路 ：
     * 即，双指针思想，指针p1和p2分别指向子数组的初始元素位置和尾元素位置；
     */
    public long countGood(int[] nums, int k) {
        // 使用long类型来存储，防止使用int类型来统计好子数组的数目，可能会出现溢出的情况；
        long goodCount = 0L;
        // 由于nums数组的长度length为[0 , 10的5次方]，即若是仅仅使用int类型的指针便能够遍历nums数组中的所有元素；
        int length = nums.length;
        // HashMap中key用来存储当前子数组初始元素的数组位置下标i；
        // 同时value，使用List集合来存储子数组初始元素下标为i 的所有可能子数组的尾部元素下标；
        HashMap<Integer , List<Integer>> hashMap = new HashMap<>();
        for(int p1 = 0 ; p1 < length ; p1++){
            List<Integer> list = new ArrayList<>();
            for(int p2 = p1 + 1; p2 < length ; p2++){
                // 向list集合中存储子数组初始元素下标为i 的所有可能子数组的尾部元素下标；
                list.add(p2);
            }
            // 将key == p1(即，子数组初始元素对应的数组位置下标i)，value中所存储的是在key == p1情况下，所有可能的子数组的尾部元素下标
            hashMap.put(p1 ,list);
        }
        for (Map.Entry<Integer, List<Integer>> entry : hashMap.entrySet()) {
            int first = entry.getKey();
            List<Integer> valueList = entry.getValue();
            int listLength = valueList.size();
            Long count = 0L;
            for (Integer value : valueList) {
                if(count >= k){
                    goodCount++;
                    continue;
                }
                count = a(nums , first , value);
                if(count >= k){
                    goodCount ++;
                }
            }
        }
        // 遍历完所有的子数组后，直接返回goodCount（用来统计好子数组的数目）即可；
        return goodCount;
    }
    // 返回当前子数组中，满足 i < j 且 arr[i] == arr[j]条件的数目;
    private long a(int[] arr, int p1, int p2) {
        // 用于统计当前子数组arr中，满足 i < j 且 arr[i] == arr[j]条件的数目
        long count = 0L;
        for(int i = p1 ; i <= p2 ; i++){
            for(int j = i + 1 ; j <= p2 ; j++){
                if(arr[i] == arr[j]){
                    count++;
                }
            }
        }
        // 返回当前子数组中所统计到的满足 i < j 且 arr[i] == arr[j]条件的数目
        return count;
    }
}
